package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var result int

func longestUnivaluePath(root *TreeNode) int {
    result = 0
	dfs(root)
	return result
}

func dfs(n *TreeNode) int {
	if n == nil {
		return 0
	}
	left := dfs(n.Left)
	right := dfs(n.Right)
	if n.Left != nil && n.Left.Val == n.Val {
		left++
	} else {
		left = 0
	}
	if n.Right != nil && n.Right.Val == n.Val {
		right++
	} else {
		right = 0
	}
	if left + right > result {
		result = left + right
	}
	if left > right {
		return left
	}
	return right
}


func main() {
	root := &TreeNode{
		Val: 4,
		Left: &TreeNode{
			Val: 4,
		},
		Right: &TreeNode{
			Val: 4,
		},
	}
	ret := longestUnivaluePath(root)
	println(ret)
}
